/*
 * BPlusTree.cpp
 *
 *  Created on: 30 Sep, 2009
 *      Author: pankaj
 */

#include "BPlusTree.h"
#include <stdio.h>
#include <iostream>
#include<vector>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include "../common.h"


#include <fcntl.h>
#include <sys/mman.h>

//#include "../BufferManager/BufferManager.h"
//#include "../yADBMS.h"

extern BufferManager *buffer;
extern int noOfBufferFrame;
extern Database *db;

BPlusTree::BPlusTree()
{
	std::cout<<"Private Default constructor\r";
}


BPlusTree::node* BPlusTree::getNodePtr(dp nod)
{
	//FILE *fp;
	if(nod.ptr == -1)
		return NULL;
	for(unsigned int i = 0;i < _pagelist.size();i++)
	{
		if(_pagelist[i]->pageno == nod.ptr)
			return (node*)(_pagelist[i]->pageData);
	}

	Page *ret = getPage(nod.ptr);


	//newnode = (node*)(ret->pageData);
	return (node*)(ret->pageData);
}

Page* BPlusTree::getPage(long pageno)
{
	Page *ret = new Page();
	Status status = _buffer->pinPage(pageno,ret);
	if(status == error)
	{
		std::cout<<"BPlusTree::getNodePtr::error - Page Not Found\r";
	}



	node* newnode = new node;
	newnode->level = *(int*)(ret->pageData);
	newnode->no_of_keys = *(int*)(ret->pageData + sizeof(int));
	newnode->parent = *(dp*)(ret->pageData + sizeof(int)*2);
	if(newnode->level == 0)
	{
		newnode->data.ldata.prev = *(dp*)(ret->pageData + BASIC_NODE_SIZE);
		newnode->data.ldata.next = *(dp*)(ret->pageData + BASIC_NODE_SIZE + sizeof(dp));
		newnode->data.ldata.key = new unsigned char*[_nos_lnode_keys];
		newnode->data.ldata.record = new rid[_nos_lnode_keys];
		for(int i=0;i<((node*)(ret->pageData))->no_of_keys;i++)
		{
			copyKey((unsigned char*)(ret->pageData + BASIC_NODE_SIZE + BASIC_LNODE_SIZE + i * _keysize),&newnode->data.ldata.key[i]);
			newnode->data.ldata.record[i] = *(rid*)(ret->pageData + BASIC_NODE_SIZE + BASIC_LNODE_SIZE + _nos_lnode_keys * _keysize + i*sizeof(rid));
		}
		//newnode->junkdata = new unsigned char[PAGE_SIZE - sizeof(newnode)];//(_nos_lnode_keys * (_keysize + sizeof(rid)) +  BASIC_NODE_SIZE + BASIC_LNODE_SIZE)];
	}
	else
	{
		newnode->data.idata.key = new unsigned char*[_fanout];
		newnode->data.idata.ptr = new dp[_fanout+1];
		int j;
		for(j=0;j<((node*)(ret->pageData))->no_of_keys;j++)
		{
			copyKey((unsigned char*)(ret->pageData + BASIC_NODE_SIZE + BASIC_INODE_SIZE + j * _keysize),&newnode->data.idata.key[j]);
			newnode->data.idata.ptr[j] = *(dp*)(ret->pageData + BASIC_NODE_SIZE + BASIC_INODE_SIZE + _fanout * _keysize + j * sizeof(dp));
		}
		newnode->data.idata.ptr[j] = *(dp*)(ret->pageData + BASIC_NODE_SIZE + BASIC_INODE_SIZE + _fanout * _keysize + j * sizeof(dp));
		//newnode->junkdata = new unsigned char[PAGE_SIZE - sizeof(newnode)];//(_fanout * (_keysize + sizeof(dp)) + sizeof(dp) + BASIC_NODE_SIZE +BASIC_INODE_SIZE)];
	}
//	free(ret->pageData);
	ret->pageData = (unsigned char*)newnode;
	_pagelist.push_back(ret);
	return ret;
}

BPlusTree::node* BPlusTree::getNodePtr(dp nod,int dirty)
{
	//FILE *fp;
	if(nod.ptr == -1)
		return NULL;
	for(unsigned int i = 0;i < _pagelist.size();i++)
	{
		if(_pagelist[i]->pageno == nod.ptr)
			return (node*)(_pagelist[i]->pageData);
	}

	Page *ret = getPage(nod.ptr);
	ret->dirty = 1;

	return (node*)(ret->pageData);
}

void BPlusTree::unPinPages()
{
	DEBUG_MSG("BPlusTree::unPinPages()%s\r","");
	int size = _pagelist.size();
	unsigned char* pagedata = NULL;
	for(int i=0;i< size;i++)
	{
//		if(pagedata != NULL)
//			free(pagedata);
//		if(pagedata == NULL)
			pagedata = new unsigned char[PAGE_SIZE];
		//unsigned char* pagedata = (unsigned char*)malloc(PAGE_SIZE*sizeof(unsigned char));
		node *newnode = (node*)(_pagelist[i]->pageData);

		*(int*)(pagedata) = newnode->level;
		*(int*)(pagedata + sizeof(int)) = newnode->no_of_keys;
		*(dp*)(pagedata + sizeof(int)*2) = newnode->parent;
		if(((node*)(pagedata))->level == 0)
		{
			*(dp*)(pagedata + BASIC_NODE_SIZE) = newnode->data.ldata.prev;
			*(dp*)(pagedata + BASIC_NODE_SIZE + sizeof(dp)) = newnode->data.ldata.next;
//			newnode->data.ldata.key = new unsigned char*[_nos_lnode_keys];
//			newnode->data.ldata.record = new rid[_nos_lnode_keys];
			for(int i=0;i<(newnode)->no_of_keys;i++)
			{
				for(int k = 0;k < _keysize;k++)
					*(unsigned char*)(pagedata + BASIC_NODE_SIZE + BASIC_LNODE_SIZE + (i * _keysize) + k) = newnode->data.ldata.key[i][k];

				*(rid*)(pagedata + BASIC_NODE_SIZE + BASIC_LNODE_SIZE + _nos_lnode_keys * _keysize + i*sizeof(rid)) = newnode->data.ldata.record[i];
			}
			//newnode->junkdata = new unsigned char[PAGE_SIZE - sizeof(newnode)];//(_nos_lnode_keys * (_keysize + sizeof(rid)) +  BASIC_NODE_SIZE + BASIC_LNODE_SIZE)];
		}
		else
		{
			int j;
			for(j=0;j<((node*)(pagedata))->no_of_keys;j++)
			{
				for(int k = 0;k < _keysize;k++)
					*(unsigned char*)(pagedata + BASIC_NODE_SIZE + BASIC_INODE_SIZE + (j * _keysize)+k) = newnode->data.idata.key[j][k];

				*(dp*)(pagedata + BASIC_NODE_SIZE + BASIC_INODE_SIZE + _fanout * _keysize + j * sizeof(dp)) = newnode->data.idata.ptr[j];
			}
			*(dp*)(pagedata + BASIC_NODE_SIZE + BASIC_INODE_SIZE + _fanout * _keysize + j * sizeof(dp)) = newnode->data.idata.ptr[j];
			//newnode->junkdata = new unsigned char[PAGE_SIZE - sizeof(newnode)];//(_fanout * (_keysize + sizeof(dp)) + sizeof(dp) + BASIC_NODE_SIZE +BASIC_INODE_SIZE)];
		}
		free(_pagelist[i]->pageData);
		_pagelist[i]->pageData =  pagedata;

		_buffer->unpinPage(_pagelist[i]->pageno,0);
//		free(pagedata);
	}
	//iterator itr = _pagelist.begin();
	//while(itr)
	//_pagelist.erase(_pagelist.begin(),_pagelist.end());
	_pagelist.clear();
}

void BPlusTree::setNodePtr(dp* rnodedp,node* rnode)
{
	if(rnode == NULL)
		rnodedp->ptr = -1;
}

void BPlusTree::setRoot(dp root)
{
	_root = root;
	dp roothead;
	roothead.ptr = _rootheadpage;
	node* head = getNodePtr(roothead,1);
	*(long*)head = _root.ptr;
}


void BPlusTree::copyKey(unsigned char* skey,unsigned char** dkey)
{
	*dkey = new unsigned char[_keysize];
	for(int i=0;i < _keysize;i++)
	{
		(*dkey)[i] = skey[i];
	}
}


//BPlusTree::BPlusTree(int fanout,unsigned char* keyformat,int nos_key_attr)
//{
//	init(fanout,keyformat,nos_key_attr);
//}

void BPlusTree::init(int fanout,unsigned char* keyformat,int nos_key_attr)
{
	bool flag=false	;
	_buffer = buffer;
	//Status status;

	//_buffer = new BufferManager(mydatabase::dbname,10000,status,NULL);
	_keyformat = (unsigned char*)malloc(1);
	_keyformat = new unsigned char[1];
	_keysize = 0;
	_nos_key_attr = nos_key_attr;
	for(int i=0;i<nos_key_attr;i++)
	{
		_keyformat = (unsigned char*)realloc(_keyformat,i+1);
		_keyformat[i] = keyformat[i];

		if(flag)
		{
			flag=false;
			_keysize += keyformat[i];
			continue;
		}
		else
			switch(keyformat[i])
			{
			case INTEGER:
				_keysize += INTEGER_SIZE;
				break;
			case LONG:
				_keysize += LONG_SIZE;
				break;
			case FLOAT:
				_keysize += FLOAT_SIZE;
				break;
			case STRING:
			case VARCHAR:
				flag = true;
				nos_key_attr++;
				break;
			case DATE:
				_keysize += 4;
				break;
			case TIME:
				_keysize += 4;
				break;
			}

		DEBUG_MSG("i=%d, ",i);
		DEBUG_MSG("keyformat=%d, ",keyformat[i]);
		DEBUG_MSG("keysize=%d\r",_keysize);
	}
	if(fanout == -1)
	{
		_fanout = (PAGE_SIZE - (BASIC_NODE_SIZE+BASIC_INODE_SIZE+sizeof(dp))) / (_keysize + sizeof(dp));
		_nos_lnode_keys = (PAGE_SIZE - (BASIC_NODE_SIZE+BASIC_LNODE_SIZE)) / (_keysize + sizeof(rid));
	}
	else
	{
		_fanout = fanout;
		_nos_lnode_keys = _fanout;
	}
	//edit
	//std::cout<<_keyformat<<"\r"	;

	_root.ptr = NULL;


	//_node_size = ((_keysize + sizeof(yadbms_BPlusTree_ns::dp)) * _fanout) + sizeof(yadbms_BPlusTree_ns::n_header);

	DEBUG_MSG("BPlusTree:B+ Tree initialized with keysize = %d\r",_keysize);
}

BPlusTree::BPlusTree(int fanout,unsigned char* keyformat,int nos_key_attr,int rootheadpage)
{
	init(fanout,keyformat,nos_key_attr);
	//_root.pageno = root_page;
	//_root.slotno = root_slot;
	_rootheadpage = rootheadpage;
	dp roothead;
	roothead.ptr = _rootheadpage;
	node* head = getNodePtr(roothead);
	_root.ptr = *(long*)head;
//	std::cout<<"\rRoot Page: "<<_root.ptr<<std::endl;
}

BPlusTree::BPlusTree(int fanout,unsigned char* keyformat,int nos_key_attr,int *rootheadpage)
{
	init(fanout,keyformat,nos_key_attr);
	Page * page = new Page();
	int pageno;
	Status status=_buffer->newPage(pageno,page);
	if(status == error)
	{
		std::cout<<"BPlusTree::BPlusTree:: Error in creating header for root\r";
		return;
	}
	_rootheadpage = pageno;
	*rootheadpage = _rootheadpage;

	dp roothead;
	roothead.ptr = _rootheadpage;
	node *root;
	dp rootdp = createNewNode(0);
	root = getNodePtr(rootdp);
	_root = rootdp;
	root->data.ldata.next.ptr = -1;
	root->data.ldata.prev.ptr = -1;
	root->parent.ptr = -1;
	*(long*)(page->pageData) = _root.ptr;


	/* for having buffer mgr capability ********************/
	/*
	int result;


	fd = open("index.txt", O_RDWR | O_CREAT | O_TRUNC, (mode_t)0600);
	if (fd == -1) {
		perror("Error opening file for writing");
		exit(EXIT_FAILURE);
	}

	result = lseek(fd, PAGE_SIZE * 102400, SEEK_SET);
	if (result == -1) {
		close(fd);
		perror("Error calling lseek() to 'stretch' the file");
		exit(EXIT_FAILURE);
	}
	//	char *temp;
	//	sprintf(temp,"%d",EOF);
	result = write(fd, "", 1);
	if (result != 1) {
		close(fd);
		perror("Error writing last byte of the file");
		exit(EXIT_FAILURE);
	}

	mmapp = (unsigned char*)mmap(0, PAGE_SIZE * 102400, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
	if (mmapp == MAP_FAILED) {
		close(fd);
		perror("Error mmapping the file");
		exit(EXIT_FAILURE);
	}

	node *root = (node*)mmapp;
	root->level = 0;
	root->no_of_keys = 0;
	root->parent.ptr = -1;
	setNodePtr(&root->data.ldata.prev,NULL);
	setNodePtr(&root->data.ldata.next,NULL);

	//	node *test = (node*)mmapp;
	//	std::cout<<"test level = "<<test->level;

	//	unsigned char* test = new unsigned char(PAGE_SIZE);
	//	node *root = (node*)test;
	//	root->level = 1;
	//	root->no_of_keys = 0;
	//
	//	FILE *fp = fopen("inddex.txt","w+");
	//	fwrite(root,PAGE_SIZE,1,fp);
	//	fclose(fp);
	//
	//	fp = fopen("inddex.txt","r");
	//	fread(root,PAGE_SIZE,1,fp);
	//	std::cout<<"heyy level = "<<root->level;
	//	fclose(fp);
	 ************************************************************/
}

int BPlusTree::keyComp(unsigned char* key1,unsigned char* key2)
{
	//	int i;
	//	for(i=0;key1[i] != '\0';i++)
	//	{
	//		if(key1[i] != key2[i])
	//			return (key1[i] - key2[i]);
	//	}
	//	if(key1[i] != key2[i])
	//		return (key1[i] - key2[i]);
	int k=0;
	int j=0;
	int l = _nos_key_attr;
	for(int i=0;i<l;i++)
	{
		switch(_keyformat[k])
		{
		case INTEGER:
			if(*((int*)(key1+j)) != *((int*)(key2+j)))
			{
				return *((int*)(key1+j)) - *((int*)(key2+j));
			}
			k++;
			j += INTEGER_SIZE;
			break;

		case LONG:
			if(*((long*)(key1+j)) != *((long*)(key2+j)))
			{
				return *((long*)(key1+j)) - *((long*)(key2+j));
			}
			k++;
			j += LONG_SIZE;
			break;

		case FLOAT:
			if(*((float*)(key1+j)) != *((float*)(key2+j)))
			{
				return *((float*)(key1+j)) - *((float*)(key2+j));
			}
			k++;
			j += FLOAT_SIZE;
			break;
		case STRING:
		case VARCHAR:
		{
			l++;
			int size = _keyformat[++k];
			for(int m=0;m<size;m++){
				if(*((key1+j+m)) != *((key2+j+m)))
				{
					return *((key1+j+m)) - *((key2+j+m));
				}
			}
			k++;
			j += size;
			break;
		}

		}
	}
	return 0;
}

void BPlusTree::printKey(unsigned char* key)
{
	int k=0;
	int j=0;
	for(int i=0;i<_nos_key_attr;i++)
	{
		switch(_keyformat[k])
		{
		case INTEGER:
			std::cout<<*((int*)(key+j))<<((i == _nos_key_attr -1)?"":";");
			k++;
			j += INTEGER_SIZE;
			break;

		case LONG:
			std::cout<<*((long*)(key+j))<<((i == _nos_key_attr -1)?"":";");
			k++;
			j += LONG_SIZE;
			break;

		case FLOAT:
			std::cout<<*((float*)(key+j))<<((i == _nos_key_attr -1)?"":";");
			k++;
			j += FLOAT_SIZE;
			break;

		}
	}
}

void BPlusTree::updateChildInfo(node* rnode,dp rnodedp)
{
	if(rnode->level == 0)
	{
		return;
	}
	else
	{
		node* child;
		for(int i=0;i<rnode->no_of_keys+1;i++)
		{
			child = getNodePtr(rnode->data.idata.ptr[i],1);
			if(child != NULL)
			{
				child->parent = rnodedp;
			}
		}
	}
}
BPlusTree::dp BPlusTree::splitNode(node* rnode,dp rnodedp,unsigned char* key,void* child)
{
	DEBUG_MSG("bpt:splitnode%s\r","");
	dp newnodedp = createNewNode(rnode->level);
	node* newnodesib = getNodePtr(newnodedp,1);
	node* ret = NULL;
	dp retdp;
	if(rnode->level == 0)
	{
		int mid = round(_nos_lnode_keys/2)+1;
		bool flag = false;
		bool flag2 = false;
		for(int i=0;i<_nos_lnode_keys;i++)
		{
			if(i < mid)
			{
				if(!flag && keyComp(rnode->data.ldata.key[i],key) >= 0)
				{
					if(_nos_lnode_keys % 2 == 1)
					{
						copyKey(rnode->data.ldata.key[_nos_lnode_keys-1],&newnodesib->data.ldata.key[mid-1]);
						newnodesib->data.ldata.record[mid-1] = rnode->data.ldata.record[_nos_lnode_keys-1];
					}
					else
					{
						copyKey(rnode->data.ldata.key[_nos_lnode_keys-1],&newnodesib->data.ldata.key[mid-2]);
						newnodesib->data.ldata.record[mid-2] = rnode->data.ldata.record[_nos_lnode_keys-1];
					}
					for(int j=_nos_lnode_keys-1;j>i;j--)
					{
						copyKey(rnode->data.ldata.key[j-1],&rnode->data.ldata.key[j]);
						rnode->data.ldata.record[j] = rnode->data.ldata.record[j-1];

					}
					copyKey(key,&rnode->data.ldata.key[i]);
					rnode->data.ldata.record[i] = *((rid*)child);
					//rnode->no_of_keys++;
					//rnode->no_of_keys--;
					ret = rnode;
					retdp = rnodedp;
					flag = true;
					continue;
				}
			}
			else
			{

				if(!flag && keyComp(rnode->data.ldata.key[i],key) >= 0)
				{
					copyKey(key,&newnodesib->data.ldata.key[i-mid]);
					newnodesib->data.ldata.record[i-mid] = *((rid*)child);
					newnodesib->no_of_keys++;
					//rnode->no_of_keys--;
					flag = true;
					flag2 = true;
					ret = newnodesib;
					retdp = newnodedp;
					//continue;
				}
				if(flag2)
				{
					copyKey(rnode->data.ldata.key[i],&newnodesib->data.ldata.key[i-mid+1]);
					newnodesib->data.ldata.record[i-mid+1] = rnode->data.ldata.record[i];
				}
				else
				{
					copyKey(rnode->data.ldata.key[i],&newnodesib->data.ldata.key[i-mid]);
					newnodesib->data.ldata.record[i-mid] = rnode->data.ldata.record[i];
				}
			}


		}
		if(!flag)
		{
			copyKey(key,&newnodesib->data.ldata.key[(_nos_lnode_keys % 2 == 1)?mid-1:mid-2]);
			newnodesib->data.ldata.record[(_nos_lnode_keys % 2 == 1)?mid-1:mid-2] = *((rid*)child);
			ret = newnodesib;
			retdp = newnodedp;
		}
		rnode->no_of_keys = mid;
		newnodesib->no_of_keys = _nos_lnode_keys+1-mid;

		if(getNodePtr(rnode->data.ldata.next) != NULL)
			getNodePtr(rnode->data.ldata.next,1)->data.ldata.prev = newnodedp;
		newnodesib->data.ldata.next = rnode->data.ldata.next;
		newnodesib->data.ldata.prev = rnodedp;
		rnode->data.ldata.next = newnodedp;
		dp parentdp = rnode->parent;
		node* parent = getNodePtr(rnode->parent,1);
		dp lchild,rchild;
		setNodePtr(&lchild,NULL);
		if(parent == NULL)
		{
			parentdp = createNewNode(rnode->level + 1);
			parent = getNodePtr(parentdp);
			parent->no_of_keys = 0;
			lchild = rnodedp;
			//(parent->prev).ptr = rnode;
		}
		rchild = newnodedp;
		parentdp = insertInode(parent,parentdp,newnodesib->data.ldata.key[0],lchild,rchild);
		parent = getNodePtr(parentdp);
		if(getNodePtr(lchild) != NULL)
		{
			rnode->parent = parentdp;
			//_root = parentdp;
			setRoot(parentdp);

		}
		newnodesib->parent = parentdp;
		updateChildInfo(newnodesib,newnodedp);
		return retdp;
	}
	else
	{

		int mid = round(_fanout/2)+1;
		bool flag = false;
		bool flag2 = false;
		for(int i=0;i<_fanout;i++)
		{
			if(i < mid)
			{
				if(!flag && keyComp(rnode->data.idata.key[i],key) >= 0)
				{
					if(_fanout % 2 == 1)
					{
						copyKey(rnode->data.idata.key[_fanout-1],&newnodesib->data.idata.key[mid-1]);
						newnodesib->data.idata.ptr[mid-1+1] = rnode->data.idata.ptr[_fanout-1+1];
					}
					else
					{
						copyKey(rnode->data.idata.key[_fanout-1],&newnodesib->data.idata.key[mid-2]);
						newnodesib->data.idata.ptr[mid-2+1] = rnode->data.idata.ptr[_fanout-1+1];
					}
					for(int j=_fanout-1;j>=i;j--)
					{
						//						copyKey(rnode->data.idata.key[j-1],&rnode->data.idata.key[j]);
						//						rnode->data.idata.ptr[j+1] = rnode->data.idata.ptr[j];
						copyKey(rnode->data.idata.key[j],&rnode->data.idata.key[j+1]);
						rnode->data.idata.ptr[j+2] = rnode->data.idata.ptr[j+1];

					}
					copyKey(key,&rnode->data.idata.key[i]);
					rnode->data.idata.ptr[i+1] = *((dp*)child);
					//rnode->no_of_keys++;
					//rnode->no_of_keys--;
					ret = rnode;
					retdp = rnodedp;
					flag = true;
					continue;
				}
			}
			else
			{

				if(!flag && keyComp(rnode->data.idata.key[i],key) >= 0)
				{
					copyKey(key,&newnodesib->data.idata.key[i-mid]);
					newnodesib->data.idata.ptr[i-mid+1] = *((dp*)child);
					newnodesib->no_of_keys++;
					//rnode->no_of_keys--;
					flag = true;
					flag2 = true;
					ret = newnodesib;
					retdp = newnodedp;
					//continue;
				}
				if(flag2)
				{
					copyKey(rnode->data.idata.key[i],&newnodesib->data.idata.key[i-mid+1]);
					newnodesib->data.idata.ptr[i-mid+1+1] = rnode->data.idata.ptr[i+1];
				}
				else
				{
					copyKey(rnode->data.idata.key[i],&newnodesib->data.idata.key[i-mid]);
					newnodesib->data.idata.ptr[i-mid+1] = rnode->data.idata.ptr[i+1];
				}

				//			newnodesib->no_of_keys++;
				//			rnode->no_of_keys--;
			}


		}
		if(!flag)
		{
			copyKey(key,&newnodesib->data.idata.key[(_fanout % 2 == 1)?mid-1:mid-2]);
			newnodesib->data.idata.ptr[1 + (_fanout % 2 == 1)?mid-1+1:mid-2+2] = *((dp*)child);
			ret = newnodesib;
			retdp = newnodedp;
		}
		rnode->no_of_keys = mid;
		newnodesib->no_of_keys = _fanout-mid+1;
		setNodePtr(&(newnodesib->data.idata.ptr[0]),NULL);
		dp parentdp = rnode->parent;
		node* parent = getNodePtr(rnode->parent,1);

		dp lchild,rchild;
		setNodePtr(&lchild, NULL);
		if(parent == NULL)
		{
			parentdp = createNewNode(rnode->level + 1);
			parent = getNodePtr(parentdp);
			parent->no_of_keys = 0;
			lchild = rnodedp;
			//(parent->prev).ptr = rnode;
		}
		rchild = newnodedp;
		parentdp = insertInode(parent,parentdp,newnodesib->data.idata.key[0],lchild,rchild);
		parent = getNodePtr(parentdp);
		if(getNodePtr(lchild) != NULL)
		{
			rnode->parent = parentdp;
			//_root = parentdp;
			setRoot(parentdp);
		}
		newnodesib->parent = parentdp;
		updateChildInfo(newnodesib,newnodedp);
		return retdp;
	}

}

BPlusTree::dp BPlusTree::insertLnode(node* rnode,dp rnodedp,unsigned char* key,rid record)
{
	DEBUG_MSG("in bpt:insertLNode%s\r","");
	DEBUG_MSG("in bpt:insertLNode rid->page%d\r",record.pageno);
	if(rnode->level == 0)
	{
		if(rnode->no_of_keys == 0)
		{
			DEBUG_MSG("BPlusTree: Inserting 1st node at 0th position%s\r","");

			rnode->data.ldata.key = new unsigned char*[_nos_lnode_keys];
			rnode->data.ldata.record = new rid[_nos_lnode_keys];

			copyKey(key,&rnode->data.ldata.key[0]);
			rnode->data.ldata.record[0] = record;
			rnode->no_of_keys = 1;
			//rnode->data.ldata.prev.ptr = NULL;
			//rnode->data.ldata.next.ptr = NULL;
			//rnode->parent.ptr = NULL;
			return rnodedp;
		}
		if(rnode->no_of_keys == _nos_lnode_keys)
		{
			//TODO:SPLIT NODE
			dp ret = splitNode(rnode,rnodedp,key,&record);
			return ret;
		}
		int i;
		for(i=0;i<rnode->no_of_keys;i++)
		{
			if(keyComp(key,rnode->data.ldata.key[i]) <= 0)
			{
				DEBUG_MSG("BPlusTree: Inserting node at i = %d\r",i);
				int k;
				for( k=rnode->no_of_keys;k>=i+1;k--)
				{
					rnode->data.ldata.key[k] = rnode->data.ldata.key[k-1];
					rnode->data.ldata.record[k] = rnode->data.ldata.record[k-1];
				}
				copyKey(key,&rnode->data.ldata.key[i]);
				rnode->data.ldata.record[i] = record;
				rnode->no_of_keys++;
				return rnodedp;
			}
		}
		DEBUG_MSG("BPlusTree: Inserting node at i = %d\r",i);
		copyKey(key,&rnode->data.ldata.key[i]);
		rnode->data.ldata.record[i] = record;
		rnode->no_of_keys++;
		return rnodedp;
	}
	return rnodedp;

}
BPlusTree::dp BPlusTree::insertInode(node* rnode,dp rnodedp,unsigned char*key,dp lchild,dp rchild)
{
	if(rnode->level > 0)
	{
		if(rnode->no_of_keys == 0)
		{
			DEBUG_MSG("BPlusTree: Inserting 1st node at 0th position%s\r","");

			rnode->data.idata.key = new unsigned char*[_fanout];
			rnode->data.idata.ptr = new dp[_fanout+1];

			copyKey(key,&rnode->data.idata.key[0]);
			rnode->data.idata.ptr[0] = lchild;
			rnode->data.idata.ptr[1] = rchild;

			rnode->no_of_keys = 1;
			//rnode->parent.ptr = NULL;
			return rnodedp;
		}
		if(rnode->no_of_keys == _fanout)
		{
			dp ret = splitNode(rnode,rnodedp,key,&rchild);
			return ret;
		}
		int i;
		for(i=0;i<rnode->no_of_keys;i++)
		{
			if(keyComp(key,rnode->data.idata.key[i]) < 0)
			{
				DEBUG_MSG("BPlusTree: Inserting node at i = %d\r",i);
				int k;
				for( k=rnode->no_of_keys;k>=i+1;k--)
				{
					rnode->data.idata.key[k] = rnode->data.idata.key[k-1];
					rnode->data.idata.ptr[k+1] = rnode->data.idata.ptr[k-1+1];
				}
				copyKey(key,&rnode->data.idata.key[k]);
				if(getNodePtr(rchild) != NULL)
					rnode->data.idata.ptr[k+1] = rchild;
				if(getNodePtr(lchild) != NULL)
					rnode->data.idata.ptr[k] = lchild;

				rnode->no_of_keys++;
				return rnodedp;
			}
		}
		DEBUG_MSG("BPlusTree: Inserting node at i = %d\r",i);
		copyKey(key,&rnode->data.idata.key[i]);
		if(getNodePtr(rchild) != NULL)
			rnode->data.idata.ptr[i+1] = rchild;
		if(getNodePtr(lchild) != NULL)
			rnode->data.idata.ptr[i] = lchild;
		rnode->no_of_keys++;
		return rnodedp;
	}
	return rnodedp;
}


void BPlusTree::insert(unsigned char* key,yadbms_common::rid record)
{
	DEBUG_MSG("in bpt:insert, key - %s\r",(char*)key);
	if(DEBUG) printKey(key);
	dp root_handledp = searchNode(key);
	node* root_handle = getNodePtr(root_handledp,1);
	if(root_handle== NULL)
	{
		DEBUG_MSG("BPlusTree: Tree is empty, Cannot proceed%s\r","");
		//BufferManager::
		unPinPages();
		return;
	}
	if(root_handle->level == 0)		//for 1st key of b+ tree
	{
		insertLnode(root_handle,root_handledp,key,record);
		unPinPages();
		return;
	}
	DEBUG_MSG("bpt:insert-error%s\r","");
}

BPlusTree::dp BPlusTree::createNewNode(int levelno)
{
	Page *newpage = new Page();
	int pageno;
	Status status;
	dp newpagedp;
	status = _buffer->newPage(pageno,newpage);

	if(status == error)
	{
		std::cout<<"BPT::createNewNode::Error in creating new page\r";
		newpagedp.ptr = -1;
		return newpagedp;
	}
	newpage->dirty = 1;
	newpagedp.ptr = pageno;
	//BPlusTree::node* newnode = new node;
	node* newnode = new node;//(node*)newpage->pageData;
	newnode->no_of_keys = 0;
	newnode->level = levelno;
	newnode->parent.ptr = -1;
	if(levelno == 0)
	{
		newnode->data.ldata.key = new unsigned char*[_nos_lnode_keys];

		for(int i=0;i<_nos_lnode_keys;i++)
		{
			newnode->data.ldata.key[i] = new unsigned char[_keysize];
		}
		newnode->data.ldata.record = new rid[_nos_lnode_keys];
		//newnode->junkdata = new unsigned char[PAGE_SIZE - sizeof(newnode)];//(_nos_lnode_keys * (_keysize + sizeof(rid)) +  BASIC_NODE_SIZE + BASIC_LNODE_SIZE)];
	}
	else
	{
		newnode->data.idata.key = new unsigned char*[_fanout];

		for(int i=0;i<_fanout;i++)
		{
			newnode->data.idata.key[i] = new unsigned char[_keysize];
		}
		newnode->data.idata.ptr = new dp[_fanout+1];
		//newnode->junkdata = new unsigned char[PAGE_SIZE - sizeof(newnode)];//(_fanout * (_keysize + sizeof(dp)) + sizeof(dp) +  BASIC_NODE_SIZE + BASIC_INODE_SIZE)];
	}
	newpage->pageData = (unsigned char*)newnode;
	_pagelist.push_back(newpage);
	/******** for buffer mgr **********/
	/*
	max_pageno++;

	node *temp = (node*)(mmapp + (max_pageno * PAGE_SIZE));
	temp->level = levelno;
	setNodePtr(&(temp->parent),NULL);
	if(levelno == 0)
	{
		temp->data.ldata.key = new unsigned char*[_nos_lnode_keys];
		temp->data.ldata.record = new rid[_nos_lnode_keys];


	}
	else
	{
		temp->data.idata.key = new unsigned char*[_fanout];
		temp->data.idata.ptr = new dp[_fanout];

	}
	dp newpage;
	newpage.ptr = max_pageno;
	 **************/

	return newpagedp;//newnode;
}

BPlusTree::dp BPlusTree::searchNode(unsigned char * key)
{
	node* root_handle = (node*)getNodePtr(_root);
	dp root_handledp = _root;
	dp nulldp;
	setNodePtr(&nulldp,NULL);
	if(root_handle== NULL)
	{
		DEBUG_MSG("BPlusTree: Tree is empty, Cannot proceed%s\r","");
		//BufferManager::
		return nulldp;
	}
	if(root_handle->level == 0)		//for 1st key of b+ tree
	{
		return root_handledp;
	}
	for(int i = root_handle->level;i>=0;i--)
	{
		if(i==0)
		{
			while(true)
			{
				bool flag = false;
				for(int j=root_handle->no_of_keys-1;j>=0;j--)
				{
					if(keyComp(key,root_handle->data.ldata.key[j]) > 0)
					{
						flag = true;
						break;
					}
				}
				if(!flag)
				{
					dp tempdp = root_handle->data.ldata.prev;
					if(getNodePtr(tempdp) == NULL)
					{
						break;
					}
					root_handledp = root_handle->data.ldata.prev;
					root_handle = getNodePtr(root_handledp);
				}
				else
				{
					break;
				}
			}
			return root_handledp;
		}
		int j;
		node* newroot = NULL;
		dp  newrootdp;

		for(j=0;j<root_handle->no_of_keys;j++)
		{
			//if(keyComp(key,root_handle->data.idata.key[j])  <= 0)
			if(keyComp(key,root_handle->data.idata.key[j])  < 0)
			{
				newroot = (node*)getNodePtr(root_handle->data.idata.ptr[j]);
				if(newroot == NULL)
				{
					if(keyComp(key,root_handle->data.idata.key[j])  < 0)
					{
						dp prevdp = getPrevINode(root_handle,root_handledp);
						node* prev = getNodePtr(prevdp);
						newrootdp = prev->data.idata.ptr[prev->no_of_keys];
						newroot = (node*)getNodePtr(newrootdp);
					}
					else
					{
						newroot = (node*)getNodePtr(root_handle->data.idata.ptr[j+1]);
						newrootdp = root_handle->data.idata.ptr[j+1];
					}

				}
				else
				{
					newrootdp = root_handle->data.idata.ptr[j];
				}

				break;
			}
		}
		//		}
		if(newroot == NULL)
		{
			root_handledp = root_handle->data.idata.ptr[j];
			root_handle = (node*)getNodePtr(root_handle->data.idata.ptr[j]);

		}

		else
		{
			root_handle = newroot;
			root_handledp = newrootdp;
		}
	}
	return nulldp;
}

BPlusTree::rid BPlusTree::search(unsigned char* key)
{
	rid ret;
	dp expnodedp = searchNode(key);
	node* expnode = getNodePtr(expnodedp);
	if(expnode == NULL)
	{
		ret.pageno = -1;
		unPinPages();
		return ret;
	}

	while(true)
	{
		if(expnode == NULL)
			break;
		for(int j=0;j<expnode->no_of_keys;j++)
		{
			if(!keyComp(key,expnode->data.ldata.key[j]))
			{
				ret = expnode->data.ldata.record[j];
				return ret;
			}
			else if(keyComp(key,expnode->data.ldata.key[j]) < 0)
			{
				ret.pageno = -1;
				return ret;
			}
		}
		expnode = getNodePtr(expnode->data.ldata.next);
	}
	ret.pageno = -1;
	unPinPages();
	return ret;
}

int BPlusTree::search(unsigned char* key,std::vector<searchresult> *vrid)
{
	dp expnodedp = searchNode(key);
	node* expnode = getNodePtr(expnodedp);
	if(expnode == NULL)
	{
		unPinPages();
		return 0;
	}
	searchresult temp;
	int count = 0;

	while(true)
	{
		if(expnode == NULL)
			break;
		for(int j=0;j<expnode->no_of_keys;j++)
		{
			if(!keyComp(key,expnode->data.ldata.key[j]))
			{
				copyKey(expnode->data.ldata.key[j],&temp.key);
				temp.record = expnode->data.ldata.record[j];
				vrid->push_back(temp);
				count++;
			}
			else if(keyComp(key,expnode->data.ldata.key[j]) < 0)
			{
				return count;
			}
		}
		expnode = getNodePtr(expnode->data.ldata.next);
	}
	unPinPages();
	return count;
}

int BPlusTree::rangeSearch(unsigned char* key1,unsigned char* key2,std::vector<searchresult> *vrid,int mode1,int mode2)
{
	if(key1 == NULL && key2 == NULL)
		return -1;
	if(mode1 == EQUAL && key2 == NULL)
	{
		return search(key1,vrid);
	}
	dp fexpnodedp,lexpnodedp;
	node* fexpnode,*lexpnode;

	if(key1 == NULL)
	{
		fexpnode = NULL;
	}
	else
	{
		fexpnodedp = searchNode(key1);
		fexpnode = getNodePtr(fexpnodedp);
	}
	if(key2 == NULL)
	{
		lexpnode = NULL;
	}
	else
	{
		lexpnodedp = searchNode(key2);
		lexpnode = getNodePtr(lexpnodedp);
	}
	int count=0;
	searchresult temp;
	if(fexpnode != NULL)
	{

		while(true)
		{
			if(fexpnode == NULL)
				break;
			for(int j=0;j<fexpnode->no_of_keys;j++)
			{
				if(((mode1 == INCLUDE && keyComp(key1,fexpnode->data.ldata.key[j]) <= 0)\
						|| (mode1 == EXCLUDE && keyComp(key1,fexpnode->data.ldata.key[j]) < 0))\
						&& (key2 == NULL \
								|| ((mode2 == INCLUDE && keyComp(key2,fexpnode->data.ldata.key[j]) >= 0)\
										|| (mode2 == EXCLUDE && keyComp(key2,fexpnode->data.ldata.key[j]) > 0))))
				{
					copyKey(fexpnode->data.ldata.key[j],&temp.key);
					temp.record = fexpnode->data.ldata.record[j];
					vrid->push_back(temp);
					count++;
				}
				else if(key2 != NULL && keyComp(key2,fexpnode->data.ldata.key[j]) < 0)
				{
					unPinPages();
					return count;
				}
			}
			fexpnode = getNodePtr(fexpnode->data.ldata.next);
		}
	}
	else
	{
		while(true)
		{
			bool flag=false;
			if(lexpnode == NULL)
				break;
			for(int j=0;j<lexpnode->no_of_keys;j++)
			{
				if(keyComp(key2,lexpnode->data.ldata.key[j]) < 0)
				{
					flag=true;
				}
			}
			if(flag || lexpnode->data.ldata.next.ptr == -1)
				break;
			lexpnode = getNodePtr(lexpnode->data.ldata.next);
		}
		while(true)
		{
			if(lexpnode == NULL)
				break;
			for(int j=lexpnode->no_of_keys-1;j>=0;j--)
			{
				if((mode2 == INCLUDE && keyComp(key2,lexpnode->data.ldata.key[j]) >= 0)\
						|| (mode2 == EXCLUDE && keyComp(key2,lexpnode->data.ldata.key[j]) > 0))
				{
					copyKey(lexpnode->data.ldata.key[j],&temp.key);
					temp.record = lexpnode->data.ldata.record[j];
					vrid->push_back(temp);
					count++;
				}
			}
			lexpnode = getNodePtr(lexpnode->data.ldata.prev);
		}
		unPinPages();
		return count;
	}
	unPinPages();
	return count;
}

bool BPlusTree::compareRid(rid rid1,rid rid2)
{
	if(rid1.pageno == rid2.pageno && rid1.slotno == rid2.slotno)
		return true;
	else
		return false;
}

bool BPlusTree::compareDp(dp dp1,dp dp2)
{
	if(dp1.ptr == dp2.ptr)
		return true;
	else
		return false;
}

bool BPlusTree::deleteEntry(unsigned char* key,rid record)
{
	//	DEBUG_MSG("bpt:In deleteEntry - key%s\r",key);
	dp expnodedp = searchNode(key);
	node* expnode = getNodePtr(expnodedp,1);
	dp ret = deleteLNode(expnode,expnodedp,key,record);
	if(getNodePtr(ret) == NULL){
		unPinPages();
		return false;
	}
	unPinPages();
	return true;
}

BPlusTree::dp BPlusTree::deleteLNode(node* expnode,dp expnodedp,unsigned char* key,rid record)
{
	DEBUG_MSG("bpt:In deleteLNode - key%s\r","");
	if(DEBUG) {
		printKey(key);
		std::cout<<"\r";
	}
	node* firstleaf = expnode;
	dp firstleafdp = expnodedp;
	dp nullnode;
	setNodePtr(&nullnode,NULL);
	if(expnode == NULL)
	{
		return nullnode;
	}
	bool isfound = false;
	int j;
	int occfirstoff = -1;
	dp occfirstdp = firstleafdp;
	node*occfirst = firstleaf;
	while(true)
	{
		if(expnode == NULL)
			break;
		for(j=0;j<expnode->no_of_keys;j++)
		{
			if(occfirstoff == -1 && !keyComp(key,expnode->data.ldata.key[j]))
			{
				occfirstoff = j;
				occfirstdp = expnodedp;
				occfirst = expnode;
			}
			if(!keyComp(key,expnode->data.ldata.key[j]) && compareRid(expnode->data.ldata.record[j],record))
			{
				isfound = true;
				break;
			}
			else if(keyComp(key,expnode->data.ldata.key[j]) < 0)
			{
				return nullnode;
			}
		}
		if(isfound)
			break;
		expnodedp = expnode->data.ldata.next;
		expnode = getNodePtr(expnodedp,1);

	}
	if(!isfound)
		return nullnode;
	//if(expnode->no_of_keys < _nos_lnode_keys/2 + 1)
	if(!compareDp(occfirstdp,expnodedp))
	{
		//TODO: copy key from expnode to firstleafdp and assign expnode = firstleafdp
		//unsigned char* tempkey;
		rid temp;
		temp = occfirst->data.ldata.record[occfirstoff];
		occfirst->data.ldata.record[occfirstoff] = expnode->data.ldata.record[j];
		expnode->data.ldata.record[j] = temp;

		expnodedp = occfirstdp;
		expnode = occfirst;
		j=occfirstoff;

	}
	//	else
	{
		//TODO: deleteLnode()
		node* next = getNodePtr(expnode->data.ldata.next,1);
		node* prev = getNodePtr(expnode->data.ldata.prev,1);
		if(expnode->no_of_keys > _nos_lnode_keys/2 + 1 || (next == NULL && prev == NULL)) //No merge condition
		{
			for(int i = j;i<expnode->no_of_keys-1;i++)
			{
				copyKey(expnode->data.ldata.key[i+1],&expnode->data.ldata.key[i]);
				expnode->data.ldata.record[i] = expnode->data.ldata.record[i+1];
			}
			expnode->no_of_keys--;
			if(j==0)
				updateParents(expnode,expnodedp);
			return expnodedp;
		}
		else
		{


			if(next != NULL && next->no_of_keys > _nos_lnode_keys/2 + 1)
			{
				int i;
				for(i = j;i<expnode->no_of_keys-1;i++)
				{
					copyKey(expnode->data.ldata.key[i+1],&expnode->data.ldata.key[i]);
					expnode->data.ldata.record[i] = expnode->data.ldata.record[i+1];
				}
				copyKey(next->data.ldata.key[0],&expnode->data.ldata.key[i]);
				expnode->data.ldata.record[i] = next->data.ldata.record[0];
				for(int k=0;k<next->no_of_keys -1 ;k++)
				{
					copyKey(next->data.ldata.key[k+1],&next->data.ldata.key[k]);
					next->data.ldata.record[k] = next->data.ldata.record[k+1];
				}
				next->no_of_keys--;
				if(j==0)
					updateParents(expnode,expnodedp);
				updateParents(next,expnode->data.ldata.next);
				return expnodedp;
			}
			else if(prev != NULL && prev->no_of_keys > _nos_lnode_keys/2 + 1)
			{
				int i;
				for(i = j;i>0;i--)
				{
					copyKey(expnode->data.ldata.key[i-1],&expnode->data.ldata.key[i]);
					expnode->data.ldata.record[i] = expnode->data.ldata.record[i-1];
				}
				copyKey(prev->data.ldata.key[prev->no_of_keys - 1],&expnode->data.ldata.key[i]);
				expnode->data.ldata.record[i] = prev->data.ldata.record[prev->no_of_keys - 1];

				prev->no_of_keys--;
				updateParents(expnode,expnodedp);
				return expnodedp;
			}
			else
			{
				//TODO: MERGING REQUIRED..
				//				mergeNode()
				if(next != NULL)
				{
					int i;
					for(i = j;i<expnode->no_of_keys-1;i++)
					{
						copyKey(expnode->data.ldata.key[i+1],&expnode->data.ldata.key[i]);
						expnode->data.ldata.record[i] = expnode->data.ldata.record[i+1];
					}
					for(int k=0;k<next->no_of_keys ;k++)
					{
						copyKey(next->data.ldata.key[k],&expnode->data.ldata.key[k+i]);
						expnode->data.ldata.record[k+i] = next->data.ldata.record[k];
					}
					expnode->no_of_keys = expnode->no_of_keys - 1 + next->no_of_keys;
					dp nextdp = expnode->data.ldata.next;
					node* nextnext;
					if((nextnext = getNodePtr(next->data.ldata.next,1)) != NULL)
						nextnext->data.ldata.prev = expnodedp;
					expnode->data.ldata.next = next->data.ldata.next;
					dp ret = deleteINode(next,nextdp);//TODO:
					if(getNodePtr(ret) == NULL)
					{
						//_root = expnodedp;
						setRoot(expnodedp);
						setNodePtr(&expnode->parent,NULL);
					}
					if(j==0)
						updateParents(expnode,expnodedp);
					deletePage(nextdp);
					return expnodedp;
				}
				else if(prev != NULL)
				{
					int i;
					int k=0;
					for(i = 0;i<expnode->no_of_keys;i++)
					{
						if(i==j)
							continue;
						else
						{
							copyKey(expnode->data.ldata.key[i],&prev->data.ldata.key[prev->no_of_keys + k]);
							prev->data.ldata.record[prev->no_of_keys + k] = expnode->data.ldata.record[i];
							k++;
						}
					}

					prev->no_of_keys = expnode->no_of_keys - 1 + prev->no_of_keys;
					dp prevdp = expnode->data.ldata.prev;
					//					if(getNodePtr(expnode->data.ldata.next) != NULL)
					//						getNodePtr(expnode->data.ldata.next)->data.ldata.prev = prevdp;
					prev->data.ldata.next = expnode->data.ldata.next;
					dp ret = deleteINode(expnode,expnodedp);
					if(getNodePtr(ret) == NULL)
					{
						//_root = prevdp;
						setRoot(prevdp);
						setNodePtr(&prev->parent,NULL);
					}
					//updateParents(prev,prevdp);
					deletePage(expnodedp);
					return prevdp;

				}
			}

		}
	}
	return nullnode;
}

BPlusTree::dp BPlusTree::deleteINode(node* rnode,dp rnodedp)
{
	DEBUG_MSG("bpt:deleteINode%s\r","");
	dp expnodedp = rnode->parent;
	node* expnode = getNodePtr(expnodedp,1);
	dp firstleafdp = expnodedp;
	dp nullnode;
	setNodePtr(&nullnode,NULL);
	if(expnode == NULL)
	{
		return nullnode;
	}

	int j;

	if(expnode == NULL)
		return nullnode;
	for(j=0;j<expnode->no_of_keys+1;j++)
	{
		if(compareDp(expnode->data.idata.ptr[j],rnodedp))
		{
			break;
		}

	}
	DEBUG_MSG("bpt:deleteINode-found at j = %d\r",j);
	dp nextdp = getNextINode(expnode,expnodedp);
	dp prevdp = getPrevINode(expnode,expnodedp);
	node* next = getNodePtr(nextdp,1);
	node* prev = getNodePtr(prevdp,1);

	if(expnode->no_of_keys > _fanout/2 + 1 || (prev == NULL && next == NULL)) //No merge condition
	{
		if(expnode->no_of_keys == 1)
		{
			DEBUG_MSG("bpt:deleteINode-Root is deleted%s\r","");
			deletePage(expnodedp);
			return nullnode;

		}
		int i;
		if(j == 0)
		{
			for(i = j;i<expnode->no_of_keys-1;i++)
			{
				copyKey(expnode->data.idata.key[i+1],&expnode->data.idata.key[i]);
				expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
			}
			expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
			updateParents(expnode,expnodedp);
		}
		else
		{
			for(i = j-1;i<expnode->no_of_keys-1;i++)
			{
				copyKey(expnode->data.idata.key[i+1],&expnode->data.idata.key[i]);
				expnode->data.idata.ptr[i+1] = expnode->data.idata.ptr[i+1+1];
			}
			//expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
		}
		expnode->no_of_keys--;
		return expnodedp;
	}
	else
	{

		if(next != NULL && next->no_of_keys > _fanout/2 + 1)
		{
			int i;
			if(j == 0)
			{
				for(i = j;i<expnode->no_of_keys-1;i++)
				{
					copyKey(expnode->data.idata.key[i+1],&expnode->data.idata.key[i]);
					expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
				}
				expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
				//i++;
			}
			else
			{
				for(i = j-1;i<expnode->no_of_keys-1;i++)
				{
					copyKey(expnode->data.idata.key[i+1],&expnode->data.idata.key[i]);
					expnode->data.idata.ptr[i+1] = expnode->data.idata.ptr[i+1+1];
				}
			}
			copyKey(next->data.idata.key[0],&expnode->data.idata.key[i]);
			expnode->data.idata.ptr[i+1] = next->data.idata.ptr[1];
			for(int k=0;k<next->no_of_keys - 1;k++)
			{
				copyKey(next->data.idata.key[k+1],&next->data.idata.key[k]);
				next->data.idata.ptr[k+1] = next->data.idata.ptr[k+1+1];
			}
			next->no_of_keys--;
			if(j==0)
				updateParents(expnode,expnodedp);
			updateParents(next,nextdp);
			updateChildInfo(expnode,expnodedp);
			return expnodedp;
		}
		else if(prev != NULL && prev->no_of_keys > _fanout/2 + 1)
		{
			int i;
			if(j > 1)
			{
				for(i = j-1;i>0;i--)
				{
					//					copyKey(expnode->data.idata.key[i-2],&expnode->data.idata.key[i-1]);
					//					expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i-1];
					copyKey(expnode->data.idata.key[i-1],&expnode->data.idata.key[i]);
					expnode->data.idata.ptr[i+1] = expnode->data.idata.ptr[i-1+1];
				}
				//expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
			}
			copyKey(prev->data.idata.key[prev->no_of_keys-1],&expnode->data.idata.key[0]);
			expnode->data.idata.ptr[1] = prev->data.idata.ptr[prev->no_of_keys];

			prev->no_of_keys--;
			updateParents(expnode,expnodedp);
			updateChildInfo(expnode,expnodedp);
			return expnodedp;
		}
		else
		{
			//TODO: MERGING REQUIRED..
			//				mergeNode()
			if(next != NULL)
			{
				int i;
				if(j == 0)
				{
					for(i = j;i<expnode->no_of_keys-1;i++)
					{
						copyKey(expnode->data.idata.key[i+1],&expnode->data.idata.key[i]);
						expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
					}
					expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
				}
				else
				{
					for(i = j-1;i<expnode->no_of_keys-1;i++)
					{
						copyKey(expnode->data.idata.key[i+1],&expnode->data.idata.key[i]);
						expnode->data.idata.ptr[i+1] = expnode->data.idata.ptr[i+1+1];
					}
					//					expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];
				}
				for(int k=0;k<next->no_of_keys;k++)
				{
					copyKey(next->data.idata.key[k],&expnode->data.idata.key[k+i]);
					expnode->data.idata.ptr[k+i+1] = next->data.idata.ptr[k+1];
				}
				expnode->no_of_keys = expnode->no_of_keys - 1 + next->no_of_keys;
				dp ret = deleteINode(next,nextdp);
				if(getNodePtr(ret) == NULL)
				{
					//_root = expnodedp;
					setRoot(expnodedp);
					setNodePtr(&expnode->parent,NULL);
				}
				updateChildInfo(expnode,expnodedp);
				deletePage(nextdp);
				return expnodedp;
			}
			else if(prev != NULL)
			{
				int i;
				int k=0;

				for(i = 0;i<expnode->no_of_keys;i++)
				{
					if(i == j-1)
						continue;
					else
					{
						copyKey(expnode->data.idata.key[i],&prev->data.idata.key[prev->no_of_keys + k]);
						prev->data.idata.ptr[prev->no_of_keys + k + 1] = expnode->data.idata.ptr[i+1];
						k++;
					}

				}
				//expnode->data.idata.ptr[i] = expnode->data.idata.ptr[i+1];

				prev->no_of_keys = prev->no_of_keys + expnode->no_of_keys -1;

				dp ret = deleteINode(expnode,expnodedp);
				if(getNodePtr(ret) == NULL)
				{
					//_root = prevdp;
					setRoot(prevdp);
					setNodePtr(&prev->parent,NULL);
				}
				updateChildInfo(prev,prevdp);
				deletePage(expnodedp);
				return prevdp;
			}
		}

	}
	return nullnode;
}

BPlusTree::dp BPlusTree::getPrevINode(node* rnode,dp rnodedp)
{
	dp parentdp = rnode->parent;
	node* parent = getNodePtr(parentdp);
	dp nullnode;
	setNodePtr(&nullnode,NULL);
	if(parent == NULL)
		return nullnode;
	int j=0;
	for(j=0;j<parent->no_of_keys+1;j++)
	{
		if(compareDp(parent->data.idata.ptr[j],rnodedp))
		{
			break;
		}

	}
	if(j == 0)
	{
//		dp prevparentdp = getPrevINode(parent,parentdp);
//		node* prevparent = getNodePtr(prevparentdp);
		//if(prevparent == NULL)
		{
			return nullnode;
		}
		//else
		{
		//	return prevparent->data.idata.ptr[prevparent->no_of_keys+1];
		}
	}
	else if(j == 1 && getNodePtr(parent->data.idata.ptr[j-1]) == NULL)
	{
		dp prevparentdp = getPrevINode(parent,parentdp);
		node* prevparent = getNodePtr(prevparentdp);
		if(prevparent == NULL)
		{
			return nullnode;
		}
		else
		{
			return prevparent->data.idata.ptr[prevparent->no_of_keys];
		}
	}
	else
	{
		return(parent->data.idata.ptr[j-1]);
	}
}
BPlusTree::dp BPlusTree::getNextINode(node* rnode,dp rnodedp)
{
	dp parentdp = rnode->parent;
	node* parent = getNodePtr(parentdp);
	dp nullnode;
	setNodePtr(&nullnode,NULL);
	if(parent == NULL)
		return nullnode;
	int j=0;
	for(j=0;j<parent->no_of_keys+1;j++)
	{
		if(compareDp(parent->data.idata.ptr[j],rnodedp))
		{
			break;
		}

	}
	if(j == parent->no_of_keys)
	{
		dp nextparentdp = getNextINode(parent,parentdp);
		node* nextparent = getNodePtr(nextparentdp);
		if(nextparent == NULL)
		{
			return nullnode;
		}
		else
		{
			return nextparent->data.idata.ptr[1];
		}
	}
	else
	{
		return(parent->data.idata.ptr[j+1]);
	}
}

void BPlusTree::deletePage(dp pageno)
{
	_buffer->freePage(pageno.ptr);
	return;
}



void BPlusTree::updateParents(node* rnode,dp rnodedp)
{
	node* parent = getNodePtr(rnode->parent,1);
	if(parent == NULL)
	{
		DEBUG_MSG("bpt:updateParents:Error-parent not found%s\r","");
		return;
	}
	if(rnode->level == 0)
	{
		int i;
		for(i=0;i<parent->no_of_keys+1;i++)
		{
			if(compareDp(parent->data.idata.ptr[i],rnodedp))
				break;
		}
		if(i == 0)
		{
			DEBUG_MSG("bpt:updateParents:Nothing to update%s\r","");
			return;
		}
		copyKey(rnode->data.ldata.key[0],&parent->data.idata.key[i-1]);
		if(getNodePtr(parent->parent) != NULL)
			updateParents(parent,parent->parent);
	}
	else
	{
		int i;
		for(i=0;i<parent->no_of_keys+1;i++)
		{
			if(compareDp(parent->data.idata.ptr[i],rnodedp))
				break;
		}
		if(i == 0)
		{
			DEBUG_MSG("bpt:updateParents:Nothing to update%s\r","");
			return;
		}
		copyKey(rnode->data.idata.key[0],&parent->data.idata.key[i-1]);
		if(getNodePtr(parent->parent) != NULL)
			updateParents(parent,parent->parent);
	}
}

void BPlusTree::printTree()
{
	printTreeRec(_root);
	unPinPages();
}

void BPlusTree::printTreeRec(dp rnodedp)
{
	node* rnode = getNodePtr(rnodedp);
	if(rnode == NULL)
		return;

	node* root_handle = rnode;
	printTreeNode(rnodedp);
	if(root_handle->level > 0)
	{
		for(int j=0;j<root_handle->no_of_keys+1;j++)
		{

			//root_handle = (node*)(root_handle->data.idata.ptr[j].ptr);
			printTreeRec(root_handle->data.idata.ptr[j]);
		}
	}

}


void BPlusTree::printTreeNode(dp rnodedp)
{
	node* root_handle = getNodePtr(rnodedp);
	for(int i = root_handle->level;i>=0;i--)
	{
		std::cout<<"\t";
	}
	//std::cout<<"level="<<root_handle->level<<"\t";
	//std::cout<<"nos_keys="<<root_handle->no_of_keys<<"\r";
	for(int i = root_handle->level;i>=0;i--)
	{
		std::cout<<"\t";
	}
	std::cout<<"me-["<<rnodedp.ptr<<"] "<<"parent-["<<root_handle->parent.ptr<<"] ";
	if(root_handle->level == 0)
	{

		for(int j=0;j<root_handle->no_of_keys;j++)
		{
			std::cout<<"{";
			printKey(root_handle->data.ldata.key[j]);
			std::cout<<"}"<<" ["<<root_handle->data.ldata.record[j].pageno<<"]\t";
		}
		std::cout<<"next-["<<root_handle->data.ldata.next.ptr<<"] "<<"prev-["<<root_handle->data.ldata.prev.ptr<<"]";
	}
	else
	{
		std::cout<<"["<<root_handle->data.idata.ptr[0].ptr<<"] ";
		for(int j=0;j<root_handle->no_of_keys;j++){
			std::cout<<"{";
			printKey(root_handle->data.idata.key[j]);
			std::cout<<"} ["<<root_handle->data.idata.ptr[j+1].ptr<<"]\t";
		}
	}
	std::cout<<"\r";
	unPinPages();

}

void BPlusTree::printNode(dp rnodedp)
{
	node* root_handle = getNodePtr(rnodedp);

	std::cout<<"Page No. - "<<rnodedp.ptr<<std::endl;

	if(root_handle->level == 0)
	{
		std::cout<<"Node Type. - "<<"Leaf"<<std::endl;
		std::cout<<"Nos Keys - "<<root_handle->no_of_keys<<std::endl;
		std::cout<<"Parent - "<<root_handle->parent.ptr<<std::endl;
		std::cout<<"\rSq No.\t    Key\t\tRid\r";
		for(int j=0;j<root_handle->no_of_keys;j++)
		{

			//			std::cout<<"Key No. - "<<j<<"\t"<<root_handle->data.ldata.key[j]<<" "<<"["<<root_handle->data.ldata.record[j].pageno<<","<<root_handle->data.ldata.record[j].slotno<<"]\r";
			std::cout<<j<<"\t";printKey(root_handle->data.ldata.key[j]);std::cout<<"\t"<<"["<<root_handle->data.ldata.record[j].pageno<<","<<root_handle->data.ldata.record[j].slotno<<"]\r";
		}
		std::cout<<"Next Page - "<<root_handle->data.ldata.next.ptr<<"\t"<<"\rPrev Page - "<<root_handle->data.ldata.prev.ptr<<"\r";
	}
	else
	{
		std::cout<<"Node Type. - "<<"Non-Leaf"<<std::endl;
		std::cout<<"Nos Keys - "<<root_handle->no_of_keys<<std::endl;
		std::cout<<"Parent - "<<root_handle->parent.ptr<<std::endl;
		std::cout<<"\rSeq No.\tPage Ptr         Key\r";
		//		std::cout<<"Page Ptr No.- 0\t"<<root_handle->data.idata.ptr[0].ptr<<"\r";
		std::cout<<0<<"\t"<<root_handle->data.idata.ptr[0].ptr<<"\t";
		for(int j=0;j<root_handle->no_of_keys;j++){
			//			std::cout<<"Key No. - "<<j<<"\t"<<root_handle->data.idata.key[j]<<"\rPage Ptr No.- "<<j+1<<"\t"<<root_handle->data.idata.ptr[j+1].ptr<<"\r";
			printKey(root_handle->data.idata.key[j]);
			std::cout<<"\r"<<j+1<<"\t"<<root_handle->data.idata.ptr[j+1].ptr<<"\t";
		}
	}
	std::cout<<"\r";
	unPinPages();
}

void BPlusTree::printDetails()
{
	std::cout<<"Key Size: "<<_keysize<<std::endl;
	std::cout<<"Fanout: "<<_fanout<<std::endl;
	std::cout<<"Nos Keys In Leaf Node: "<<_nos_lnode_keys<<std::endl;
	std::cout<<"Root Header Page No.: "<<_rootheadpage<<std::endl;
	std::cout<<"Root Page No.: "<<_root.ptr<<std::endl;
	unPinPages();
}

BPlusTree::dp BPlusTree::getRoot()
{
	unPinPages();
	return _root;
}

void BPlusTree::bulkLoad(long first,long last,long step)
{
	vector<dp> leafpages;
	//for (long i=first;i < last;i+=step)
	long num = first;
	dp prevdp;
	prevdp.ptr = -1;
	node* prev = NULL;
	while(num <= last)
	{
		dp newpagedp = createNewNode(0);
		node* newpage = getNodePtr(newpagedp,1);
		if(newpage == NULL)
			std::cout<<"Error: BPlusTree::bulkLoad\n";
		for(int j=0;j<_nos_lnode_keys;j++)
		{
			copyKey((unsigned char*)&num,&newpage->data.ldata.key[j]);
			newpage->data.ldata.record[j].pageno = num;
			newpage->data.ldata.record[j].slotno = 0;
			num += step;
			newpage->no_of_keys++;
		}
		newpage->data.ldata.prev = prevdp;
		if(prevdp.ptr != -1)
		{
			prev = getNodePtr(prevdp,1);
			prev->data.ldata.next = newpagedp;
		}
		prevdp = newpagedp;
		leafpages.push_back(newpagedp);
		unPinPages();
	}
	//std::cout<<"bulk: "<<leafpages.size()<<"\n";
	deletePage(_root);
	dp nroot = createNewNode(1);
	node* root = getNodePtr(nroot,1);
	root->level = 1;
	root->data.idata.ptr[0] = leafpages[0];
	root->data.idata.ptr[1] = leafpages[1];
	root->parent.ptr = -1;
	root->no_of_keys = 1;
	dp secnodedp = leafpages[1];
	node* secnode = getNodePtr(secnodedp,1);
	copyKey(secnode->data.ldata.key[0],&root->data.idata.key[0]);
//	setRoot(nroot);
	//insert
//	if()
	node* fstnode = getNodePtr(leafpages[0],1);
	fstnode->parent = _root;
	secnode->parent = _root;
	setRoot(nroot);
//	for(int i=0;i < leafpages.size();i++)
//	{
//		cout<<leafpages[i].ptr<<" ";
//	}
	for(int i=2;i < leafpages.size();i++)
	{
		dp prvdp = leafpages[i-1];
		node* prv = getNodePtr(prvdp);
		dp parentdp = prv->parent;
		node* parent = getNodePtr(parentdp,1);
		dp currdp = leafpages[i];
		node* curr = getNodePtr(currdp,1);
		dp lch;
		lch.ptr = -1;
		parentdp = insertInode(parent,parentdp,curr->data.ldata.key[0],lch,currdp);
		parent = getNodePtr(parentdp,1);
//		curr->parent = parentdp;
		updateChildInfo(parent,parentdp);
		unPinPages();
	}


}

BPlusTree::~BPlusTree() {
	// TODO Auto-generated destructor stub
	/*	if (munmap(mmapp, PAGE_SIZE * 102400) == -1) {
		perror("Error un-mmapping the file");*/

	/* Decide here whether to close(fd) and exit() or not. Depends... */
	//}
	//close(fd);
	//unPinPages();
	//_buffer->flushAllPages();
}
